<?php
/**
 * @title 1584. 连接所有点的最小费用 - 排序
 * @author start2004
 */

ini_set("memory_limit", "1280M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param Integer[][] $points
     * @return Integer
     */
    function minCostConnectPoints($points) {
        /**
         * @since 2020-10-22 长度
         */
        $len = count($points);

        /**
         * @since 2020-10-22 2点之间距离
         */
        $ds = [];
        $lines = [];
        for($i=0; $i<$len-1; $i++){
            for($j=$i+1; $j<$len; $j++){
                $d = abs($points[$i][0]-$points[$j][0]) + abs($points[$i][1]-$points[$j][1]);
                $ds[] = $d;
                $lines[] = [$i, $j];
            }
        }
        // return $lines;

        /**
         * @since 2020-10-22 排序
         */
        array_multisort($ds, SORT_DESC, SORT_NUMERIC, $lines);
        // return [$ds, $lines];
        // return $lines;

        /**
         * @since 2020-10-22 结果集
         */
        $result = 0;

        /**
         * @since 2020-10-22 每个点对应区间
         */
        $areas = [];

        /**
         * @since 2020-10-22 已经存在的点
         */
        $existsPoints = [];
        $existsNum = 0;
        $val = 0;
        while( ($points = array_pop($lines)) !== null ){
            $d = array_pop($ds);
            list($p1, $p2) = $points;
            // echo "p1={$p1}, p2={$p2}, d={$d}, ";

            /**
             * @since 2020-10-22 2个全新的点
             */
            if(!isset($existsPoints[$p1]) AND !isset($existsPoints[$p2])){
                $existsPoints[$p1] = $val;
                $existsPoints[$p2] = $val;
                $areas[$val][] = $p1;
                $areas[$val][] = $p2;

                if($existsNum == 0){
                    $existsNum += 2;
                } else {
                    $existsNum++;
                }
                $result += $d;
                $val++;
                // echo "都不存在, +2d/+d", PHP_EOL;
            } else {
                /**
                 * @since 2020-10-22 2个点都存在
                 */
                if(isset($existsPoints[$p1]) AND isset($existsPoints[$p2])){
                    /**
                     * @since 2020-10-22 不同区间
                     */
                    if($existsPoints[$p1] != $existsPoints[$p2]){
                        $v1 = $existsPoints[$p1];
                        $v2 = $existsPoints[$p2];

                        /**
                         * @since 2020-10-22 确保v2是较少的区间组
                         */
                        if(count($areas[$v2]) > count($areas[$v1])){
                            list($v2, $v1) = [$v1, $v2];
                        } else {}

                        /**
                         * @since 2020-10-22 v2区间变成v1
                         */
                        foreach ($areas[$v2] as $p){
                            $existsPoints[$p] = $v1;
                            $areas[$v1][] = $p;
                        }
                        $existsNum++;

                        // echo "都存在, 不同区间, +d", PHP_EOL;
                        $result += $d;
                    } else {
                        // echo "都存在, 同区间", PHP_EOL;
                    }
                } else {
                    /**
                     * @since 2020-10-22 只有1个点存在
                     */
                    // echo "只有1个点存在, +d", PHP_EOL;
                    // $existsPoints[$p1] = 1;
                    // $existsPoints[$p2] = 1;
                    if(isset($existsPoints[$p1])){
                        $existsPoints[$p2] = $existsPoints[$p1];
                        $areas[$existsPoints[$p1]][] = $p2;
                    } else {
                        $existsPoints[$p1] = $existsPoints[$p2];
                        $areas[$existsPoints[$p2]][] = $p1;
                    }
                    $result += $d;
                    $existsNum++;
                }
            }

            /**
             * @since 2020-10-22 所有点选上
             */
            // echo "existsNum={$existsNum}, len={$len}", PHP_EOL;
            if($existsNum == $len){
                break;
            } else {}
        }

        /**
         * @return
         */
        return $result;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202010/2020.10.22_3.php
 */

// $data = [];
// echo "[";
// for($i=1; $i<=200; $i++){
//     $x = mt_rand(0, 100000);
//     $y = mt_rand(0, 100000);
//     $data[] = [$x, $y];
//     echo "[{$x}, {$y}],";
// }
// echo "],";die();
// var_dump($data);die();

$datas = [
    [
        [[48134, 8482],[26495, 8331],[9221, 95426],[54756, 45654],[41588, 15132],[16144, 68172],[36391, 41745],[18688, 30256],[41148, 32440],[806, 74562],[18962, 89706],[55601, 27107],[91675, 41531],[23098, 11321],[65079, 43149],[23896, 17890],[72222, 69920],[55348, 89636],[92179, 99],[97157, 85408],[31544, 21139],[484, 28214],[49724, 11787],[12598, 61152],[51950, 60633],[57650, 23953],[3370, 4292],[39155, 2461],[47130, 15490],[58494, 40897],[64805, 6364],[40376, 48914],[57744, 9345],[45351, 85],[53334, 57081],[69536, 13093],[68560, 86278],[18424, 41046],[96246, 4729],[75711, 53126],[24056, 27055],[92354, 52931],[65090, 99951],[78971, 48193],[34302, 85992],[57080, 89852],[70140, 51410],[3415, 88209],[93531, 16559],[16714, 61067],[51022, 99235],[97862, 31583],[52142, 65752],[78488, 75892],[27201, 27900],[74528, 38446],[59307, 11206],[22128, 81621],[16406, 18742],[35932, 19012],[90290, 78305],[30395, 67337],[64044, 38870],[67511, 55300],[53409, 5796],[3690, 23367],[66839, 46687],[24995, 91695],[20654, 65861],[24208, 88863],[24551, 47595],[66297, 17458],[24788, 36545],[73853, 61322],[10619, 69838],[1296, 27088],[8124, 44790],[88252, 17678],[18128, 72216],[98921, 24504],[71406, 67947],[81495, 2936],[50341, 60174],[42922, 95845],[91823, 66515],[61504, 30243],[33463, 93622],[45958, 65107],[16586, 20412],[25286, 15675],[56343, 62991],[91683, 1498],[80186, 31502],[47016, 68053],[94222, 82449],[59630, 79149],[77622, 41923],[20943, 20858],[1865, 79719],[52069, 64831],[44703, 70200],[23009, 84642],[27067, 22287],[27073, 155],[26184, 25226],[89524, 32051],[37931, 51833],[38835, 11738],[10494, 47169],[68325, 63687],[85744, 69262],[28702, 17607],[68916, 51828],[7145, 53679],[1456, 45629],[30066, 50063],[63078, 74125],[64437, 31589],[20153, 21247],[63566, 90584],[55669, 14734],[9960, 8736],[15718, 87588],[58942, 25872],[82623, 18677],[17555, 11485],[52139, 9849],[56083, 61384],[15542, 87651],[10745, 97145],[26296, 86981],[77581, 9648],[68638, 95759],[96068, 65645],[50918, 12217],[45014, 40826],[23341, 6824],[19195, 97400],[25486, 39412],[53743, 51250],[60125, 93379],[37284, 11535],[52946, 68461],[18663, 86727],[57242, 88048],[42361, 97037],[57811, 18906],[44370, 13439],[59680, 79911],[17387, 15578],[24468, 86345],[47412, 49717],[69745, 59434],[91304, 16766],[60647, 70877],[8590, 36949],[88481, 27587],[69536, 4629],[3463, 82922],[9484, 57965],[58669, 47781],[83416, 27456],[37434, 65530],[70219, 102],[63612, 90131],[59391, 63026],[70505, 33422],[81464, 61596],[51926, 39336],[41666, 488],[9041, 35892],[11777, 69462],[21851, 83664],[49055, 90891],[18365, 12888],[97555, 20677],[24502, 74190],[25565, 34375],[21164, 5950],[51055, 42010],[61780, 46262],[96615, 31218],[14816, 74054],[77586, 2350],[70224, 73049],[88838, 52114],[42624, 76469],[4571, 86291],[71637, 11355],[77034, 52513],[9537, 86245],[6678, 46895],[33623, 79862],[39220, 85139],[10118, 39118],[50417, 19037],[76784, 42542],[50140, 5276],[97698, 53495],[40517, 9995],],],
    // [
    //     [[0,0],[2,2],[3,10],[5,2],[7,0]], // 20
    // ],
    // [
    //     [[3,12],[-2,5],[-4,1]], // 18
    // ],
    // [
    //     [[0,0],[1,1],[1,0],[-1,1]], // 4
    // ],
    // [
    //     [[-1000000,-1000000],[1000000,1000000]], // 4000000
    // ],
    // [
    //     [[0,0]], // 0
    // ],
    // [
    //     [[5,-17],[-3,-14],[-2,18],[-14,15],[-9,-17],[9,-16],[8,-3],[-15,11],[-12,17],[6,6],[4,3]], // 94
    // ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->minCostConnectPoints(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    // var_dump($result);
    if(count($result)<=20){
        var_dump($result);
    } else {
        var_dump(count($result));
    }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $result = $obj->$data[0][$i](...$data[1][$i]);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
